#ifndef COMPLEXOBJ
#define COMPLEXOBJ

#include "object.h"
#include "common.h"

#include <vector>
#include <queue>
#include <cstring>
#include <map>

struct Compare{
    static int type;
    bool operator()(Vec* a, Vec* b){
        return (*a)[type] < (*b)[type];
    }
};

struct Cuboid{
    Vec large;
    Vec small;
    Cuboid(){}
    void update(Triangle* aa){
        for (int i = 0 ; i < 3; i++){
            large[i] = max(large[i], aa->p1[i]);
            large[i] = max(large[i], aa->p2[i]);
            large[i] = max(large[i], aa->p3[i]);
            small[i] = min(small[i], aa->p1[i]);
            small[i] = min(small[i], aa->p2[i]);
            small[i] = min(small[i], aa->p3[i]);
        }
    }
    double intersect(Ray &ray){
        double dis = -1;
        for (int i = 0; i < 3; i++){
            double kk = (large[i] - ray.ori[i]) / (ray.dir[i]);
            if (kk > zero){
                Vec p = ray.getpoint(kk);
                int flag = 1;
                for (int j = 0 ; j < 3; j++){
                    if (p[j] < small[j] - EPS || p[j] > large[j] + EPS){
                        flag = 0;
                        break;
                    }
                }
                if (flag && (dis == -1 || kk < dis))
                    dis = kk;
            }

            kk = (small[i] - ray.ori[i]) / (ray.dir[i]);
            if (kk > zero){
                Vec p = ray.getpoint(kk);
                int flag = 1;
                for (int j = 0 ; j < 3; j++){
                    if (p[j] < small[j] - EPS || p[j] > large[j] + EPS){
                        flag = 0;
                        break;
                    }
                }
                if (flag && (dis == -1 || kk < dis))
                    dis = kk;
            }
        }
        return dis;
    }
};

struct Node{
    Node(){
        PointSize = faceSize = isLeaf = 0;
    }

    Cuboid cube;
    Node *leftSon, *rightSon;
    bool isLeaf;

    vector <Triangle*> face;
    vector <Vec*> point;
    int faceSize;
    int PointSize;

    bool intersect(const Ray &ray, Vec &P , Vec &N, Material &material);
    void makeKDTree(int type);

};

struct Edge{
    Edge(){
        pos = 0;
        key = 0;
    }
    int x,y;
    int pos;
    double diff;
    int key;
    Vec recom;
    void calcDiff(const vector<Vec> &point, const vector<Matrix> & Q, int* father){

        diff = 0;

        Matrix mm = Q[getFather(x, father)];
        mm += Q[getFather(y, father)];
        recom = mm.solve();
        if (recom.length() < zero){
            recom = (point[getFather(x, father)] + point[getFather(y, father)]) / 2;
        }else {
        }
        //recom = (point[getFather(x, father)] + point[getFather(y, father)]) / 2;
        double a[4] = {recom.x, recom.y, recom.z, 1};
        double b[4] = {0};
        for (int i = 0 ; i < 4; i++){
            for (int j = 0; j < 4; j++){
                b[i] += a[j] * mm.matrix[j][i];
            }
        }
        for (int i = 0; i < 4; i++){
            diff += a[i] * b[i];
        }
    }
};

struct List{
    List(){
        next = 0;
        line = 0;
    }

    Edge* line;
    int next;
};

struct ListT{
    ListT(){
        next = 0;
        face = 0;
    }

    Triangle* face;
    int next;
};

struct Heap{
    int num;
    bool flag;    // 0 为小根堆 1 为小根堆 默认 小根堆
    Edge** p;
    bool small(Edge* a, Edge* b){       // 比较函数
        if (!flag) return a->diff < b->diff;
        else return !(a->diff < b->diff);
    }
    void swap(int x, int y){
        p[x]->pos = y;
        p[y]->pos = x;
        Edge* tmp = p[x];
        p[x] = p[y];
        p[y] = tmp;
    }

    int up(int x){         // 向上换
        while (x != 1 && small(p[x], p[x / 2])){
            swap(x, x / 2);
            x /= 2;
        }
        return x;
    }
    int down(int x){      // 向下换
        while ( ( x * 2 <= num && (small(p[x * 2], p[x])) ) ||
                ((x * 2 + 1 <= num) && small(p[x * 2 + 1], p[x]))){
            int tmp = x * 2;
            if ((x * 2 + 1 <= num) && small(p[x * 2 + 1], p[x * 2]))
                tmp++;
            swap(x, tmp);
            x = tmp;
        }
        return x;
    }
    Edge* pop(){ //  弹出根
        Edge* tmp = p[1];
        if (num == 0){
            printf("!!error the heap is empty\n");
            return 0;
        }
        p[1] = p[num--];
        down(1);
        tmp->pos = -1;
        return tmp;
    }
    void insert(Edge* a){ // 插入元素
        p[++num] = a;
        a->pos = num;
        up(num);
    }

    void update(int x){
        x = up(x);
        down(x);
    }

    void del(int x){
        swap(x, num);
        p[num]->pos = -1;
        num--;
        update(x);
    }

    Heap(int size){
        num = flag = 0;
        p = new Edge*[size+5];
    }
    ~Heap(){
        delete p;
    }
};



struct ComplexObj : Object{
    ComplexObj(string file);
    ~ComplexObj();
    int pointSize;  // count from 1
    int faceSize;   // count from 0
    int materialSize;// count from 0
    int vtSize; // count from 1
    vector<Triangle> triangle;
    vector<Vec> point;
    vector<Vec> vt;

//===========for simplified===========
    int usedSize;
    int lineSize;
    int listSize;

    vector<Matrix> Q;
    int* neighborHead;
    List* neighborSet;

    int* start;
    ListT* neiFace;
    Edge* line;
    int* father;
    int* pointKey;
    Heap* heap;

    int updateKey;

    vector<Triangle*> faceBuff;
    vector<int> pointBuff;
    vector<Edge*> edgeBuff;
//===========================================


    Node* root;
//================================
    map<string, int> MTL;
    vector<Material> materials;
//================================
    void makeKDTree(Node* cur);

    bool intersect(const Ray &ray, Vec &P , Vec &N, Material &material);

    void inse(int x, int y);
    void inn(int x, Triangle* tt);
    void updateP(const int &x, const int &updateKey);
    void updateQ(Triangle& tt);

    void simplified(double rate);
    int merge(Edge *cur);


    void readMtlFile(string file);

    int getFather(int x){
        return ::getFather(x, father);
    }

    void output(string file);
};

#endif // COMPLEXOBJ

